
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 2098. -- [Usaco2010]Bigmac周游世界的巨无霸 -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>2098: [Usaco2010]Bigmac周游世界的巨无霸</h2><span class=green>Time Limit: </span>10 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>64 MB<br><span class=green>Submit: </span>21&nbsp;&nbsp;<span class=green>Solved: </span>0<br>[<a href='submitpage.php?id=2098'>Submit</a>][<a href='problemstatus.php?id=2098'>Status</a>][<a href='bbs.php?id=2098'>Discuss</a>]</center><h2>Description</h2><div class=content>
Bessie正在牛学院(cowllege)学习她最爱的课程：宏观经济学。为了准备她的毕业课题，
她要发表一篇关于国家之间汇率的研究报告。

为了使得她的报告更加生动，她将展示世界各地的巨无霸的价格(虽然她极其
讨厌这些不健康的垃圾食品)。通过给出巨无霸在某个国家的价格和一些国家
货币之间的汇率，Bessie想知道一个巨无霸在某个国家的最便宜的价格。

下面看个例子：

* 一个巨无霸在美国售价60美刀。

* 美刀对加拿大元的的汇率是0.2，也就是1美刀可以兑换0.2加拿大元

* 美刀对英镑的汇率是5.00，也就是1美刀可以兑换5.00英镑

* 英镑对加拿大元的汇率是0.5，也就是1英镑可以兑换0.5加拿大元

* 加拿大元对美刀的汇率是5.00，也就是1加拿大元可以兑换5.00美刀

Bessie想要找到在加拿大购买一个巨无霸最便宜的方式（通过货币的流通与兑换）。
以下有两种方式：

* 从美元直接兑换加拿大元，这样一个巨无霸价值
  60 美刀 * 0.2 加拿大元 / 1 美刀 = 12 加拿大元。

* 从美元兑换成英镑，再有英镑兑换为加拿大元，这样一个巨无霸价值
  60 美刀 * 5 英镑 / 1 美元 * 0.5 加元 / 1 英镑 = 150 加元。

Bessie会选择前一种兑换方式，这样她购买一个巨无霸可以只付12加元。

Bessie在研究N (1 <= N <= 2,000) 个国家，编号为1...N。她列出了M(1 <= M<= 25,000)
种兑换方式和相对应的汇率 e_ij (0.1 < e_ij <= 10)，表示国家i和j的货币
的兑换比例是e_ij(是单向的)。

给出一个实数V (1 <= V <= 1,000,000,000,000)，表示一个巨无霸在A国(1 <= A <= N)的售价。
你能够帮助她找到一种方式使得一个巨无霸在B国(1 <= B <= N; B != A)的售价尽可能少吗？
如果售价没有最小值，输出0。

保证最终答案如果不是0，一定在1到10^15之间。

保证任何国家的货币可以兑换为任何另一个国家的货币。

</div><h2>Input</h2><div class=content>* 第1行： 5个空格分隔的数字： N, M, V, A, B

* 第2...M+1行： 三个空格分开的数字： i, j, e_ij

</div><h2>Output</h2><div class=content>
* 第1行：如果不存在最小值，为0。否则是一个正数，和标准答案的差的绝对值不能大于10^-6。
</div><h2>Sample Input</h2>
			<div class=content><span class=sampledata><br />
3 4 60 1 2<br />
1 2 0.2<br />
1 3 5<br />
3 2 0.5<br />
2 1 5<br />
<br />
<br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata>12.00<br />
</span></div><h2>HINT</h2>
			<div class=content><p></p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search=Gold'>Gold</a></p></div><center>[<a href='submitpage.php?id=2098'>Submit</a>][<a href='problemstatus.php?id=2098'>Status</a>][<a href='bbs.php?id=2098'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
